class NL

Definition

$\mathbf{NL} =$ NSPACE$(\log n)$

(for given language)

Definition

A language $L$ is in $\mathbf{NL}$ if there exists a deterministic TM $M$ (the verifier) with additional special read-once input tape, and polynomial $p: \mathbb{N} \to \mathbb{N}$ such that for every $x \in \{0,1\}^*$,

where $M(x,u)$ denotes output of $M$ where $x$ is placed on input tape, and $u$ is placed on special read-once tape, and $M$ uses at most $O(\log |x|)$ space on its read-write tapes for every input $x$.

(read once head, certificate tape)

Notes

• say language $C$ is $\mathbf{NL}$-complete if it is in $\mathbf{NL}$ and for every $B \in \mathbf{NL}$, $B \leq_l C$ (logspace reduction)

See also

• L

References

1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, pp. 81, 90.